package com.cskaoyan.javase.recursion._1basic;

/**
 * 递归的思想:
 * 引例：使用递归计算N（N>=1）的阶乘（factorial）
 *
 * 求解阶乘,首先可以用循环,不是非要用递归
 * 使用循环时,最主要的是找到循环的条件以及循环体
 * n! =  n * (n-1) * (n-2) * ... * 1;
 * 循环求解找到循环体,就是重复执行的一段代码.
 *
 * 用递归求解阶乘
 * 要想使用递归,首先就要找到递归体以及递归的出口,二者缺一不可.
 * 递归体是方法中自身调用自身方法的一条语句,这相当于把问题,分解成相同解决手段的一个更小规模的问题
 * 一个大规模的问题被分解后,一直分解,最终分解的问题足够小,就能很快直接的得出答案
 * 这就是递归体和递归的出口
 * 递归的思想就是分解问题的思想:
 *      1. 把一个复杂的大规模的问题，分解成若干相似的小规模的子问题。(递归体)
 *      2. 当子问题规模足够小的时候，就可以直接得到小规模问题的解。(递归的出口)
 *      3. 然后把所有的小规模的子问题的解，组合起来，得到要求解的大规模问题的解。
 *
 * n! = n * (n-1)!
 * (n-1)! = (n-1)*(n-2)!
 * (n-2)! = (n-2)*(n-3)!
 * ...
 * 当n = 1 时,n! = 1;
 * 递归体: n! = n * (n-1)!
 * 递归的出口: 当n = 1时,n! = 1.
 *
 * 总结一下,递归的优缺点:
 * 优点:
 *      1.递归的代码往往十分简洁优雅
 *      2.递归求解问题的思路和人解决问题的思路是类似的,很多问题,如果用递归求解会变得很简单,很易于人类的思考
 *
 * 缺点:
 *      1.递归很危险,稍有不慎就会导致栈溢出,使用递归必须小心谨慎.
 *      2.递归求解问题,会不停地调用方法,并且存在大量重复计算的部分.这就导致递归既耗费内存,占用空间,运行效率也差
 *          时间复杂度和空间复杂度都不优越,都很差.
 *
 * 总之,递归不要乱用,除非想不到更好的办法,不然不要使用递归.
 *
 * @since 10:02
 * @author wuguidong@cskaoyan.onaliyun.com
 */
public class Demo {
    public static void main(String[] args) {
        System.out.println(factorial(10));
        System.out.println(factorial2(10));
    }

    public static long factorial2(int n) {
        // 递归求解,首先写递归的出口
        if (n == 1) {
            return 1;
        }
        // 如果n不等于1,就递归求解
        return n * factorial2(n - 1);
    }

    // 使用循环求解阶乘
    public static long factorial(int n) {
        long result = 1;
        while (n > 0) {
            result *= n;
            n--;
        }
        return result;
    }
}
